home *** CD-ROM | disk | FTP | other *** search
/ SPACE 2 / SPACE - Library 2 - Volume 1.iso / program / 322 / flex / tblcmp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1988-10-20  |  40.3 KB  |  1,604 lines
  1. /* tblcmp - table compression routines */
  2.  
  3. /*
  4.  * Copyright (c) 1987, the University of California
  5.  * 
  6.  * The United States Government has rights in this work pursuant to
  7.  * contract no. DE-AC03-76SF00098 between the United States Department of
  8.  * Energy and the University of California.
  9.  * 
  10.  * This program may be redistributed.  Enhancements and derivative works
  11.  * may be created provided the new works, if made available to the general
  12.  * public, are made available for use by anyone.
  13.  */
  14.  
  15. #include "flexdef.h"
  16.  
  17. /* bldtbl - build table entries for dfa state
  18.  *
  19.  * synopsis
  20.  *   int state[numecs], statenum, totaltrans, comstate, comfreq;
  21.  *   bldtbl( state, statenum, totaltrans, comstate, comfreq );
  22.  *
  23.  * State is the statenum'th dfa state.  It is indexed by equivalence class and
  24.  * gives the number of the state to enter for a given equivalence class.
  25.  * totaltrans is the total number of transitions out of the state.  Comstate
  26.  * is that state which is the destination of the most transitions out of State.
  27.  * Comfreq is how many transitions there are out of State to Comstate.
  28.  *
  29.  * A note on terminology:
  30.  *    "protos" are transition tables which have a high probability of
  31.  * either being redundant (a state processed later will have an identical
  32.  * transition table) or nearly redundant (a state processed later will have
  33.  * many of the same out-transitions).  A "most recently used" queue of
  34.  * protos is kept around with the hope that most states will find a proto
  35.  * which is similar enough to be usable, and therefore compacting the
  36.  * output tables.
  37.  *    "templates" are a special type of proto.  If a transition table is
  38.  * homogeneous or nearly homogeneous (all transitions go to the same
  39.  * destination) then the odds are good that future states will also go
  40.  * to the same destination state on basically the same character set.
  41.  * These homogeneous states are so common when dealing with large rule
  42.  * sets that they merit special attention.  If the transition table were
  43.  * simply made into a proto, then (typically) each subsequent, similar
  44.  * state will differ from the proto for two out-transitions.  One of these
  45.  * out-transitions will be that character on which the proto does not go
  46.  * to the common destination, and one will be that character on which the
  47.  * state does not go to the common destination.  Templates, on the other
  48.  * hand, go to the common state on EVERY transition character, and therefore
  49.  * cost only one difference.
  50.  */
  51.  
  52. bldtbl( state, statenum, totaltrans, comstate, comfreq )
  53. int state[], statenum, totaltrans, comstate, comfreq;
  54.  
  55.     {
  56.     int extptr, extrct[2][CSIZE + 1];
  57.     int mindiff, minprot, i, d;
  58.     int checkcom;
  59.  
  60.     /* If extptr is 0 then the first array of extrct holds the result of the
  61.      * "best difference" to date, which is those transitions which occur in
  62.      * "state" but not in the proto which, to date, has the fewest differences
  63.      * between itself and "state".  If extptr is 1 then the second array of
  64.      * extrct hold the best difference.  The two arrays are toggled
  65.      * between so that the best difference to date can be kept around and
  66.      * also a difference just created by checking against a candidate "best"
  67.      * proto.
  68.      */
  69.  
  70.     extptr = 0;
  71.  
  72.     /* if the state has too few out-transitions, don't bother trying to
  73.      * compact its tables
  74.      */
  75.  
  76.     if ( (totaltrans * 100) < (numecs * PROTO_SIZE_PERCENTAGE) )
  77.     mkentry( state, numecs, statenum, JAMSTATE, totaltrans );
  78.  
  79.     else
  80.     {
  81.     /* checkcom is true if we should only check "state" against
  82.      * protos which have the same "comstate" value
  83.      */
  84.  
  85.     checkcom = comfreq * 100 > totaltrans * CHECK_COM_PERCENTAGE;
  86.  
  87.     minprot = firstprot;
  88.     mindiff = totaltrans;
  89.  
  90.     if ( checkcom )
  91.         {
  92.         /* find first proto which has the same "comstate" */
  93.         for ( i = firstprot; i != NIL; i = protnext[i] )
  94.         if ( protcomst[i] == comstate )
  95.             {
  96.             minprot = i;
  97.             mindiff = tbldiff( state, minprot, extrct[extptr] );
  98.             break;
  99.             }
  100.         }
  101.  
  102.     else
  103.         {
  104.         /* since we've decided that the most common destination out
  105.          * of "state" does not occur with a high enough frequency,
  106.          * we set the "comstate" to zero, assuring that if this state
  107.          * is entered into the proto list, it will not be considered
  108.          * a template.
  109.          */
  110.         comstate = 0;
  111.  
  112.         if ( firstprot != NIL )
  113.         {
  114.         minprot = firstprot;
  115.         mindiff = tbldiff( state, minprot, extrct[extptr] );
  116.         }
  117.         }
  118.  
  119.     /* we now have the first interesting proo in "minprot".  If
  120.      * it matches within the tolerances set for the first proto,
  121.      * we don't want to bother scanning the rest of the proto list
  122.      * to see if we have any other reasonable matches.
  123.      */
  124.  
  125.     if ( mindiff * 100 > totaltrans * FIRST_MATCH_DIFF_PERCENTAGE )
  126.         { /* not a good enough match.  Scan the rest of the protos */
  127.         for ( i = minprot; i != NIL; i = protnext[i] )
  128.         {
  129.         d = tbldiff( state, i, extrct[1 - extptr] );
  130.         if ( d < mindiff )
  131.             {
  132.             extptr = 1 - extptr;
  133.             mindiff = d;
  134.             minprot = i;
  135.             }
  136.         }
  137.         }
  138.  
  139.     /* check if the proto we've decided on as our best bet is close
  140.      * enough to the state we want to match to be usable
  141.      */
  142.  
  143.     if ( mindiff * 100 > totaltrans * ACCEPTABLE_DIFF_PERCENTAGE )
  144.         {
  145.         /* no good.  If the state is homogeneous enough, we make a
  146.          * template out of it.  Otherwise, we make a proto.
  147.          */
  148.  
  149.         if ( comfreq * 100 >= totaltrans * TEMPLATE_SAME_PERCENTAGE )
  150.         mktemplate( state, statenum, comstate );
  151.  
  152.         else
  153.         {
  154.         mkprot( state, statenum, comstate );
  155.         mkentry( state, numecs, statenum, JAMSTATE, totaltrans );
  156.         }
  157.         }
  158.  
  159.     else
  160.         { /* use the proto */
  161.         mkentry( extrct[extptr], numecs, statenum,
  162.              prottbl[minprot], mindiff );
  163.  
  164.         /* if this state was sufficiently different from the proto
  165.          * we built it from, make it, too, a proto
  166.          */
  167.  
  168.         if ( mindiff * 100 >= totaltrans * NEW_PROTO_DIFF_PERCENTAGE )
  169.         mkprot( state, statenum, comstate );
  170.  
  171.         /* since mkprot added a new proto to the proto queue, it's possible
  172.          * that "minprot" is no longer on the proto queue (if it happened
  173.          * to have been the last entry, it would have been bumped off).
  174.          * If it's not there, then the new proto took its physical place
  175.          * (though logically the new proto is at the beginning of the
  176.          * queue), so in that case the following call will do nothing.
  177.          */
  178.  
  179.         mv2front( minprot );
  180.         }
  181.     }
  182.     }
  183.  
  184.  
  185. /* cmptmps - compress template table entries
  186.  *
  187.  * synopsis
  188.  *    cmptmps();
  189.  *
  190.  *  template tables are compressed by using the 'template equivalence
  191.  *  classes', which are collections of transition character equivalence
  192.  *  classes which always appear together in templates - really meta-equivalence
  193.  *  classes.  until this point, the tables for templates have been stored
  194.  *  up at the top end of the nxt array; they will now be compressed and have
  195.  *  table entries made for them.
  196.  */
  197.  
  198. cmptmps()
  199.  
  200.     {
  201.     int tmpstorage[CSIZE + 1];
  202.     register int *tmp = tmpstorage, i, j;
  203.     int totaltrans, trans;
  204.  
  205.     peakpairs = numtemps * numecs + tblend;
  206.  
  207.     if ( usemecs )
  208.     {
  209.     /* create equivalence classes base on data gathered on template
  210.      * transitions
  211.      */
  212.  
  213.     nummecs = cre8ecs( tecfwd, tecbck, numecs );
  214.     }
  215.     
  216.     else
  217.     nummecs = numecs;
  218.  
  219.     if ( lastdfa + numtemps + 1 >= current_max_dfas )
  220.     increase_max_dfas();
  221.  
  222.     /* loop through each template */
  223.  
  224.     for ( i = 1; i <= numtemps; ++i )
  225.     {
  226.     totaltrans = 0;    /* number of non-jam transitions out of this template */
  227.  
  228.     for ( j = 1; j <= numecs; ++j )
  229.         {
  230.         trans = tnxt[numecs * i + j];
  231.  
  232.         if ( usemecs )
  233.         {
  234.         /* the absolute value of tecbck is the meta-equivalence class
  235.          * of a given equivalence class, as set up by cre8ecs
  236.          */
  237.         if ( tecbck[j] > 0 )
  238.             {
  239.             tmp[tecbck[j]] = trans;
  240.  
  241.             if ( trans > 0 )
  242.             ++totaltrans;
  243.             }
  244.         }
  245.  
  246.         else
  247.         {
  248.         tmp[j] = trans;
  249.  
  250.         if ( trans > 0 )
  251.             ++totaltrans;
  252.         }
  253.         }
  254.  
  255.     /* it is assumed (in a rather subtle way) in the skeleton that
  256.      * if we're using meta-equivalence classes, the def[] entry for
  257.      * all templates is the jam template, i.e., templates never default
  258.      * to other non-jam table entries (e.g., another template)
  259.      */
  260.  
  261.     /* leave room for the jam-state after the last real state */
  262.     mkentry( tmp, nummecs, lastdfa + i + 1, JAMSTATE, totaltrans );
  263.     }
  264.     }
  265.  
  266.  
  267.  
  268. /* expand_nxt_chk - expand the next check arrays */
  269.  
  270. expand_nxt_chk()
  271.  
  272.     {
  273.     register int old_max = current_max_xpairs;
  274.  
  275.     current_max_xpairs += MAX_XPAIRS_INCREMENT;
  276.  
  277.     ++num_reallocs;
  278.  
  279.     nxt = reallocate_integer_array( nxt, current_max_xpairs );
  280.     chk = reallocate_integer_array( chk, current_max_xpairs );
  281.  
  282.     bzero( (char *) (chk + old_max),
  283.        MAX_XPAIRS_INCREMENT * sizeof( int ) / sizeof( char ) );
  284.     }
  285.  
  286.  
  287. /* find_table_space - finds a space in the table for a state to be placed
  288.  *
  289.  * synopsis
  290.  *     int *state, numtrans, block_start;
  291.  *     int find_table_space();
  292.  *
  293.  *     block_start = find_table_space( state, numtrans );
  294.  *
  295.  * State is the state to be added to the full speed transition table.
  296.  * Numtrans is the number of out-transitions for the state.
  297.  *
  298.  * find_table_space() returns the position of the start of the first block (in
  299.  * chk) able to accommodate the state
  300.  *
  301.  * In determining if a state will or will not fit, find_table_space() must take
  302.  * into account the fact that an end-of-buffer state will be added at [0],
  303.  * and an action number will be added in [-1].
  304.  */
  305.  
  306. int find_table_space( state, numtrans )
  307. int *state, numtrans;
  308.     
  309.     {
  310.     /* firstfree is the position of the first possible occurrence of two
  311.      * consecutive unused records in the chk and nxt arrays
  312.      */
  313.     register int i;
  314.     register int *state_ptr, *chk_ptr;
  315.     register int *ptr_to_last_entry_in_state;
  316.  
  317.     /* if there are too many out-transitions, put the state at the end of
  318.      * nxt and chk
  319.      */
  320.     if ( numtrans > MAX_XTIONS_FOR_FULL_INTERIOR_FIT )
  321.     {
  322.     /* if table is empty, return the first available spot in chk/nxt,
  323.      * which should be 1
  324.      */
  325.     if ( tblend < 2 )
  326.         return ( 1 );
  327.  
  328.     i = tblend - numecs;    /* start searching for table space near the
  329.                  * end of chk/nxt arrays
  330.                  */
  331.     }
  332.  
  333.     else
  334.     i = firstfree;        /* start searching for table space from the
  335.                  * beginning (skipping only the elements
  336.                  * which will definitely not hold the new
  337.                  * state)
  338.                  */
  339.  
  340.     while ( 1 )        /* loops until a space is found */
  341.     {
  342.     if ( i + numecs > current_max_xpairs )
  343.         expand_nxt_chk();
  344.  
  345.     /* loops until space for end-of-buffer and action number are found */
  346.     while ( 1 )
  347.         {
  348.         if ( chk[i - 1] == 0 )    /* check for action number space */
  349.         {
  350.         if ( chk[i] == 0 )    /* check for end-of-buffer space */
  351.             break;
  352.  
  353.         else
  354.             i += 2;    /* since i != 0, there is no use checking to
  355.                  * see if (++i) - 1 == 0, because that's the
  356.                  * same as i == 0, so we skip a space
  357.                  */
  358.         }
  359.  
  360.         else
  361.         ++i;
  362.  
  363.         if ( i + numecs > current_max_xpairs )
  364.         expand_nxt_chk();
  365.         }
  366.  
  367.     /* if we started search from the beginning, store the new firstfree for
  368.      * the next call of find_table_space()
  369.      */
  370.     if ( numtrans <= MAX_XTIONS_FOR_FULL_INTERIOR_FIT )
  371.         firstfree = i + 1;
  372.  
  373.     /* check to see if all elements in chk (and therefore nxt) that are
  374.      * needed for the new state have not yet been taken
  375.      */
  376.  
  377.     state_ptr = &state[1];
  378.     ptr_to_last_entry_in_state = &chk[i + numecs + 1];
  379.  
  380.     for ( chk_ptr = &chk[i + 1]; chk_ptr != ptr_to_last_entry_in_state;
  381.           ++chk_ptr )
  382.         if ( *(state_ptr++) != 0 && *chk_ptr != 0 )
  383.         break;
  384.  
  385.     if ( chk_ptr == ptr_to_last_entry_in_state )
  386.         return ( i );
  387.  
  388.     else
  389.         ++i;
  390.     }
  391.     }
  392.  
  393.  
  394. /* genctbl - generates full speed compressed transition table
  395.  *
  396.  * synopsis
  397.  *     genctbl();
  398.  */
  399.  
  400. genctbl()
  401.  
  402.     {
  403.     register int i;
  404.  
  405.     /* table of verify for transition and offset to next state */
  406.     printf( "static struct yy_trans_info yy_transition[%d] =\n",
  407.         tblend + numecs + 1 );
  408.     printf( "    {\n" );
  409.     
  410.     /* We want the transition to be represented as the offset to the
  411.      * next state, not the actual state number, which is what it currently is.
  412.      * The offset is base[nxt[i]] - base[chk[i]].  That's just the
  413.      * difference between the starting points of the two involved states
  414.      * (to - from).
  415.      *
  416.      * first, though, we need to find some way to put in our end-of-buffer
  417.      * flags and states.  We do this by making a state with absolutely no
  418.      * transitions.  We put it at the end of the table.
  419.      */
  420.     /* at this point, we're guaranteed that there's enough room in nxt[]
  421.      * and chk[] to hold tblend + numecs entries.  We need just two slots.
  422.      * One for the action and one for the end-of-buffer transition.  We
  423.      * now *assume* that we're guaranteed the only character we'll try to
  424.      * index this nxt/chk pair with is EOB, i.e., 0, so we don't have to
  425.      * make sure there's room for jam entries for other characters.
  426.      */
  427.  
  428.     base[lastdfa + 1] = tblend + 2;
  429.     nxt[tblend + 1] = END_OF_BUFFER_ACTION;
  430.     chk[tblend + 1] = numecs + 1;
  431.     chk[tblend + 2] = 1; /* anything but EOB */
  432.     nxt[tblend + 2] = 0; /* so that "make test" won't show arb. differences */
  433.  
  434.     /* make sure every state has a end-of-buffer transition and an action # */
  435.     for ( i = 0; i <= lastdfa; ++i )
  436.     {
  437.     chk[base[i]] = EOB_POSITION;
  438.     chk[base[i] - 1] = ACTION_POSITION;
  439.     nxt[base[i] - 1] = dfaacc[i].dfaacc_state;    /* action number */
  440.     }
  441.  
  442.     for ( i = 0; i <= lastsc * 2; ++i )
  443.     nxt[base[i] - 1] = DEFAULT_ACTION;
  444.  
  445.     dataline = 0;
  446.     datapos = 0;
  447.  
  448.     for ( i = 0; i <= tblend; ++i )
  449.     {
  450.     if ( chk[i] == EOB_POSITION )
  451.         transition_struct_out( 0, base[lastdfa + 1] - i );
  452.  
  453.     else if ( chk[i] == ACTION_POSITION )
  454.         transition_struct_out( 0, nxt[i] );
  455.  
  456.     else if ( chk[i] > numecs || chk[i] == 0 )
  457.         transition_struct_out( 0, 0 );        /* unused slot */
  458.  
  459.     else    /* verify, transition */
  460.         transition_struct_out( chk[i], base[nxt[i]] - (i - chk[i]) );
  461.     }
  462.  
  463.  
  464.     /* here's the final, end-of-buffer state */
  465.     transition_struct_out( chk[tblend + 1], nxt[tblend + 1] );
  466.     transition_struct_out( chk[tblend + 2], nxt[tblend + 2] );
  467.  
  468.     printf( "    };\n" );
  469.     printf( "\n" );
  470.  
  471.     /* table of pointers to start states */
  472.     printf( "static struct yy_trans_info *yy_state_ptr[%d] =\n",
  473.     lastsc * 2 + 1 );
  474.     printf( "    {\n" );
  475.  
  476.     for ( i = 0; i <= lastsc * 2; ++i )
  477.     printf( "    &yy_transition[%d],\n", base[i] );
  478.  
  479.     printf( "    };\n" );
  480.  
  481.     if ( useecs )
  482.     genecs();
  483.     }
  484.  
  485.  
  486. /* gentabs - generate data statements for the transition tables
  487.  *
  488.  * synopsis
  489.  *    gentabs();
  490.  */
  491.  
  492. gentabs()
  493.  
  494.     {
  495.     int i, j, k, *accset, nacc, *acc_array;
  496.     char clower();
  497.  
  498.     /* *everything* is done in terms of arrays starting at 1, so provide
  499.      * a null entry for the zero element of all FTL arrays
  500.      */
  501. #ifdef atarist
  502.     static char ftl_long_decl[] = "static long int %s[%d] =\n    {   0,\n";
  503.     static char ftl_short_decl[] = "static short int %s[%d] =\n    {   0,\n";
  504.     static char ftl_char_decl[] = "static char %s[%d] =\n    {   0,\n";
  505. #else
  506.     static char ftl_long_decl[] = "static long int %c[%d] =\n    {   0,\n";
  507.     static char ftl_short_decl[] = "static short int %c[%d] =\n    {   0,\n";
  508.     static char ftl_char_decl[] = "static char %c[%d] =\n    {   0,\n";
  509. #endif
  510.  
  511.     acc_array = allocate_integer_array( current_max_dfas );
  512.     nummt = 0;
  513.  
  514.     if ( fulltbl )
  515.     jambase = lastdfa + 1;    /* home of "jam" pseudo-state */
  516.  
  517.     printf( "#define YY_JAM %d\n", jamstate );
  518.     printf( "#define YY_JAM_BASE %d\n", jambase );
  519.  
  520.     if ( usemecs )
  521.     printf( "#define YY_TEMPLATE %d\n", lastdfa + 2 );
  522.  
  523.     if ( reject )
  524.     {
  525.     /* write out accepting list and pointer list
  526.      * first we generate the ACCEPT array.  In the process, we compute
  527.      * the indices that will go into the ALIST array, and save the
  528.      * indices in the dfaacc array
  529.      */
  530.  
  531.     printf( accnum > 127 ? ftl_short_decl : ftl_char_decl,
  532.         ACCEPT, max( numas, 1 ) + 1 );
  533.  
  534.     j = 1;    /* index into ACCEPT array */
  535.  
  536.     for ( i = 1; i <= lastdfa; ++i )
  537.         {
  538.         acc_array[i] = j;
  539.  
  540.         if ( accsiz[i] != 0 )
  541.         {
  542.         accset = dfaacc[i].dfaacc_set;
  543.         nacc = accsiz[i];
  544.  
  545.         if ( trace )
  546.             fprintf( stderr, "state # %d accepts: ", i );
  547.  
  548.         for ( k = 1; k <= nacc; ++k )
  549.             {
  550.             ++j;
  551.             mkdata( accset[k] );
  552.  
  553.             if ( trace )
  554.             {
  555.             fprintf( stderr, "[%d]", accset[k] );
  556.  
  557.             if ( k < nacc )
  558.                 fputs( ", ", stderr );
  559.             else
  560.                 putc( '\n', stderr );
  561.             }
  562.             }
  563.         }
  564.         }
  565.  
  566.     /* add accepting number for the "jam" state */
  567.     acc_array[i] = j;
  568.  
  569.     dataend();
  570.     }
  571.     
  572.     else
  573.     {
  574.     for ( i = 1; i <= lastdfa; ++i )
  575.         acc_array[i] = dfaacc[i].dfaacc_state;
  576.     
  577.     acc_array[i] = 0; /* add (null) accepting number for jam state */
  578.     }
  579.  
  580.     /* spit out ALIST array.  If we're doing "reject", it'll be pointers
  581.      * into the ACCEPT array.  Otherwise it's actual accepting numbers.
  582.      * In either case, we just dump the numbers.
  583.      */
  584.  
  585.     /* "lastdfa + 2" is the size of ALIST; includes room for FTL arrays
  586.      * beginning at 0 and for "jam" state
  587.      */
  588.     k = lastdfa + 2;
  589.  
  590.     if ( reject )
  591.     /* we put a "cap" on the table associating lists of accepting
  592.      * numbers with state numbers.  This is needed because we tell
  593.      * where the end of an accepting list is by looking at where
  594.      * the list for the next state starts.
  595.      */
  596.     ++k;
  597.  
  598.     printf( ((reject && numas > 126) || accnum > 127) ?
  599.         ftl_short_decl : ftl_char_decl, ALIST, k );
  600.  
  601.     /* set up default actions */
  602.     for ( i = 1; i <= lastsc * 2; ++i )
  603.     acc_array[i] = DEFAULT_ACTION;
  604.  
  605.     acc_array[end_of_buffer_state] = END_OF_BUFFER_ACTION;
  606.  
  607.     for ( i = 1; i <= lastdfa; ++i )
  608.     {
  609.     mkdata( acc_array[i] );
  610.  
  611.     if ( ! reject && trace && acc_array[i] )
  612.         fprintf( stderr, "state # %d accepts: [%d]\n", i, acc_array[i] );
  613.     }
  614.  
  615.     /* add entry for "jam" state */
  616.     mkdata( acc_array[i] );
  617.  
  618.     if ( reject )
  619.     /* add "cap" for the list */
  620.     mkdata( acc_array[i] );
  621.  
  622.     dataend();
  623.  
  624.     if ( useecs )
  625.     genecs();
  626.  
  627.     if ( usemecs )
  628.     {
  629.     /* write out meta-equivalence classes (used to index templates with) */
  630.  
  631.     if ( trace )
  632.         fputs( "\n\nMeta-Equivalence Classes:\n", stderr );
  633.  
  634.     printf( ftl_char_decl, MATCHARRAY, numecs + 1 );
  635.  
  636.     for ( i = 1; i <= numecs; ++i )
  637.         {
  638.         if ( trace )
  639.         fprintf( stderr, "%d = %d\n", i, abs( tecbck[i] ) );
  640.  
  641.         mkdata( abs( tecbck[i] ) );
  642.         }
  643.  
  644.     dataend();
  645.     }
  646.  
  647.     if ( ! fulltbl )
  648.     {
  649.     int total_states = lastdfa + numtemps;
  650.  
  651.     printf( tblend > MAX_SHORT ? ftl_long_decl : ftl_short_decl,
  652.         BASEARRAY, total_states + 1 );
  653.  
  654.     for ( i = 1; i <= lastdfa; ++i )
  655.         {
  656.         register int d = def[i];
  657.  
  658.         if ( base[i] == JAMSTATE )
  659.         base[i] = jambase;
  660.  
  661.         if ( d == JAMSTATE )
  662.         def[i] = jamstate;
  663.  
  664.         else if ( d < 0 )
  665.         {
  666.         /* template reference */
  667.         ++tmpuses;
  668.         def[i] = lastdfa - d + 1;
  669.         }
  670.  
  671.         mkdata( base[i] );
  672.         }
  673.  
  674.     /* generate jam state's base index */
  675.     mkdata( base[i] );
  676.  
  677.     for ( ++i /* skip jam state */; i <= total_states; ++i )
  678.         {
  679.         mkdata( base[i] );
  680.         def[i] = jamstate;
  681.         }
  682.  
  683.     dataend();
  684.  
  685.     printf( tblend > MAX_SHORT ? ftl_long_decl : ftl_short_decl,
  686.         DEFARRAY, total_states + 1 );
  687.  
  688.     for ( i = 1; i <= total_states; ++i )
  689.         mkdata( def[i] );
  690.  
  691.     dataend();
  692.  
  693.     printf( lastdfa > MAX_SHORT ? ftl_long_decl : ftl_short_decl,
  694.         NEXTARRAY, tblend + 1 );
  695.  
  696.     for ( i = 1; i <= tblend; ++i )
  697.         {
  698.         if ( nxt[i] == 0 || chk[i] == 0 )
  699.         nxt[i] = jamstate;    /* new state is the JAM state */
  700.  
  701.         mkdata( nxt[i] );
  702.         }
  703.  
  704.     dataend();
  705.  
  706.     printf( lastdfa > MAX_SHORT ? ftl_long_decl : ftl_short_decl,
  707.         CHECKARRAY, tblend + 1 );
  708.  
  709.     for ( i = 1; i <= tblend; ++i )
  710.         {
  711.         if ( chk[i] == 0 )
  712.         ++nummt;
  713.  
  714.         mkdata( chk[i] );
  715.         }
  716.  
  717.     dataend();
  718.     }
  719.     }
  720.  
  721.  
  722. /* generate equivalence-class tables */
  723.  
  724. genecs()
  725.  
  726.     {
  727.     register int i, j;
  728. #ifdef atarist
  729.     static char ftl_char_decl[] = "static char %s[%d] =\n    {   0,\n";
  730. #else
  731.     static char ftl_char_decl[] = "static char %c[%d] =\n    {   0,\n";
  732. #endif
  733.     int numrows;
  734.  
  735.     printf( ftl_char_decl, ECARRAY, CSIZE + 1 );
  736.  
  737.     for ( i = 1; i <= CSIZE; ++i )
  738.     {
  739.     if ( caseins && (i >= 'A') && (i <= 'Z') )
  740.         ecgroup[i] = ecgroup[clower( i )];
  741.  
  742.     ecgroup[i] = abs( ecgroup[i] );
  743.     mkdata( ecgroup[i] );
  744.     }
  745.  
  746.     dataend();
  747.  
  748.     if ( trace )
  749.     {
  750.     fputs( "\n\nEquivalence Classes:\n\n", stderr );
  751.  
  752.     numrows = (CSIZE + 1) / 8;
  753.  
  754.     for ( j = 1; j <= numrows; ++j )
  755.         {
  756.         for ( i = j; i <= CSIZE; i = i + numrows )
  757.         {
  758.         if ( i >= 1 && i <= 31 )
  759.             fprintf( stderr, "^%c = %-2d",
  760.                  'A' + i - 1, ecgroup[i] );
  761.  
  762.         else if ( i >= 32 && i <= 126 )
  763.             fprintf( stderr, " %c = %-2d", i, ecgroup[i] );
  764.  
  765.         else if ( i == 127 )
  766.             fprintf( stderr, "^@ = %-2d", ecgroup[i] );
  767.  
  768.         else
  769.             fprintf( stderr, "\nSomething Weird: %d = %d\n", i,
  770.                  ecgroup[i] );
  771.  
  772.         putc( '\t', stderr );
  773.         }
  774.  
  775.         putc( '\n', stderr );
  776.         }
  777.     }
  778.     }
  779.  
  780.  
  781. /* inittbl - initialize transition tables
  782.  *
  783.  * synopsis
  784.  *   inittbl();
  785.  *
  786.  * Initializes "firstfree" to be one beyond the end of the table.  Initializes
  787.  * all "chk" entries to be zero.  Note that templates are built in their
  788.  * own tbase/tdef tables.  They are shifted down to be contiguous
  789.  * with the non-template entries during table generation.
  790.  */
  791. inittbl()
  792.  
  793.     {
  794.     register int i;
  795.  
  796.     bzero( (char *) chk, current_max_xpairs * sizeof( int ) / sizeof( char ) );
  797.  
  798.     tblend = 0;
  799.     firstfree = tblend + 1;
  800.     numtemps = 0;
  801.  
  802.     if ( usemecs )
  803.     {
  804.     /* set up doubly-linked meta-equivalence classes
  805.      * these are sets of equivalence classes which all have identical
  806.      * transitions out of TEMPLATES
  807.      */
  808.  
  809.     tecbck[1] = NIL;
  810.  
  811.     for ( i = 2; i <= numecs; ++i )
  812.         {
  813.         tecbck[i] = i - 1;
  814.         tecfwd[i - 1] = i;
  815.         }
  816.  
  817.     tecfwd[numecs] = NIL;
  818.     }
  819.     }
  820.  
  821.  
  822. /* make_tables - generate transition tables
  823.  *
  824.  * synopsis
  825.  *     make_tables();
  826.  *
  827.  * Generates transition tables and finishes generating output file
  828.  */
  829.  
  830. make_tables()
  831.  
  832.     {
  833.     if ( fullspd )
  834.     { /* need to define YY_TRANS_OFFSET_TYPE as a size large
  835.        * enough to hold the biggest offset
  836.        */
  837.     int total_table_size = tblend + numecs + 1;
  838.  
  839.     printf( "#define YY_TRANS_OFFSET_TYPE %s\n",
  840.         total_table_size > MAX_SHORT ? "long" : "short" );
  841.     }
  842.     
  843.     if ( fullspd || fulltbl )
  844.     skelout();
  845.  
  846.     /* compute the tables and copy them to output file */
  847.     if ( fullspd )
  848.     genctbl();
  849.  
  850.     else
  851.     gentabs();
  852.  
  853.     skelout();
  854.  
  855.     (void) fclose( temp_action_file );
  856.     temp_action_file = fopen( action_file_name, "r" );
  857.  
  858.     /* copy prolog from action_file to output file */
  859.     action_out();
  860.  
  861.     skelout();
  862.  
  863.     /* copy actions from action_file to output file */
  864.     action_out();
  865.  
  866.     skelout();
  867.  
  868.     /* copy remainder of input to output */
  869.  
  870.     line_directive_out( stdout );
  871.     (void) flexscan(); /* copy remainder of input to output */
  872.     }
  873.  
  874.  
  875. /* mkdeftbl - make the default, "jam" table entries
  876.  *
  877.  * synopsis
  878.  *   mkdeftbl();
  879.  */
  880.  
  881. mkdeftbl()
  882.  
  883.     {
  884.     int i;
  885.  
  886.     jamstate = lastdfa + 1;
  887.  
  888.     if ( tblend + numecs > current_max_xpairs )
  889.     expand_nxt_chk();
  890.  
  891.     for ( i = 1; i <= numecs; ++i )
  892.     {
  893.     nxt[tblend + i] = 0;
  894.     chk[tblend + i] = jamstate;
  895.     }
  896.  
  897.     jambase = tblend;
  898.  
  899.     base[jamstate] = jambase;
  900.  
  901.     /* should generate a run-time array bounds check if
  902.      * ever used as a default
  903.      */
  904.     def[jamstate] = BAD_SUBSCRIPT;
  905.  
  906.     tblend += numecs;
  907.     ++numtemps;
  908.     }
  909.  
  910.  
  911. /* mkentry - create base/def and nxt/chk entries for transition array
  912.  *
  913.  * synopsis
  914.  *   int state[numchars + 1], numchars, statenum, deflink, totaltrans;
  915.  *   mkentry( state, numchars, statenum, deflink, totaltrans );
  916.  *
  917.  * "state" is a transition array "numchars" characters in size, "statenum"
  918.  * is the offset to be used into the base/def tables, and "deflink" is the
  919.  * entry to put in the "def" table entry.  If "deflink" is equal to
  920.  * "JAMSTATE", then no attempt will be made to fit zero entries of "state"
  921.  * (i.e., jam entries) into the table.  It is assumed that by linking to
  922.  * "JAMSTATE" they will be taken care of.  In any case, entries in "state"
  923.  * marking transitions to "SAME_TRANS" are treated as though they will be
  924.  * taken care of by whereever "deflink" points.  "totaltrans" is the total
  925.  * number of transitions out of the state.  If it is below a certain threshold,
  926.  * the tables are searched for an interior spot that will accommodate the
  927.  * state array.
  928.  */
  929.  
  930. mkentry( state, numchars, statenum, deflink, totaltrans )
  931. register int *state;
  932. int numchars, statenum, deflink, totaltrans;
  933.  
  934.     {
  935.     register int minec, maxec, i, baseaddr;
  936.     int tblbase, tbllast;
  937.  
  938.     if ( totaltrans == 0 )
  939.     { /* there are no out-transitions */
  940.     if ( deflink == JAMSTATE )
  941.         base[statenum] = JAMSTATE;
  942.     else
  943.         base[statenum] = 0;
  944.  
  945.     def[statenum] = deflink;
  946.     return;
  947.     }
  948.  
  949.     for ( minec = 1; minec <= numchars; ++minec )
  950.     {
  951.     if ( state[minec] != SAME_TRANS )
  952.         if ( state[minec] != 0 || deflink != JAMSTATE )
  953.         break;
  954.     }
  955.  
  956.     if ( totaltrans == 1 )
  957.     {
  958.     /* there's only one out-transition.  Save it for later to fill
  959.      * in holes in the tables.
  960.      */
  961.     stack1( statenum, minec, state[minec], deflink );
  962.     return;
  963.     }
  964.  
  965.     for ( maxec = numchars; maxec > 0; --maxec )
  966.     {
  967.     if ( state[maxec] != SAME_TRANS )
  968.         if ( state[maxec] != 0 || deflink != JAMSTATE )
  969.         break;
  970.     }
  971.  
  972.     /* Whether we try to fit the state table in the middle of the table
  973.      * entries we have already generated, or if we just take the state
  974.      * table at the end of the nxt/chk tables, we must make sure that we
  975.      * have a valid base address (i.e., non-negative).  Note that not only are
  976.      * negative base addresses dangerous at run-time (because indexing the
  977.      * next array with one and a low-valued character might generate an
  978.      * array-out-of-bounds error message), but at compile-time negative
  979.      * base addresses denote TEMPLATES.
  980.      */
  981.  
  982.     /* find the first transition of state that we need to worry about. */
  983.     if ( totaltrans * 100 <= numchars * INTERIOR_FIT_PERCENTAGE )
  984.     { /* attempt to squeeze it into the middle of the tabls */
  985.     baseaddr = firstfree;
  986.  
  987.     while ( baseaddr < minec )
  988.         {
  989.         /* using baseaddr would result in a negative base address below
  990.          * find the next free slot
  991.          */
  992.         for ( ++baseaddr; chk[baseaddr] != 0; ++baseaddr )
  993.         ;
  994.         }
  995.  
  996.     if ( baseaddr + maxec - minec >= current_max_xpairs )
  997.         expand_nxt_chk();
  998.  
  999.     for ( i = minec; i <= maxec; ++i )
  1000.         if ( state[i] != SAME_TRANS )
  1001.         if ( state[i] != 0 || deflink != JAMSTATE )
  1002.             if ( chk[baseaddr + i - minec] != 0 )
  1003.             { /* baseaddr unsuitable - find another */
  1004.             for ( ++baseaddr;
  1005.                   baseaddr < current_max_xpairs &&
  1006.                   chk[baseaddr] != 0;
  1007.                   ++baseaddr )
  1008.                 ;
  1009.  
  1010.             if ( baseaddr + maxec - minec >= current_max_xpairs )
  1011.                 expand_nxt_chk();
  1012.  
  1013.             /* reset the loop counter so we'll start all
  1014.              * over again next time it's incremented
  1015.              */
  1016.  
  1017.             i = minec - 1;
  1018.             }
  1019.     }
  1020.  
  1021.     else
  1022.     {
  1023.     /* ensure that the base address we eventually generate is
  1024.      * non-negative
  1025.      */
  1026.     baseaddr = max( tblend + 1, minec );
  1027.     }
  1028.  
  1029.     tblbase = baseaddr - minec;
  1030.     tbllast = tblbase + maxec;
  1031.  
  1032.     if ( tbllast >= current_max_xpairs )
  1033.     expand_nxt_chk();
  1034.  
  1035.     base[statenum] = tblbase;
  1036.     def[statenum] = deflink;
  1037.  
  1038.     for ( i = minec; i <= maxec; ++i )
  1039.     if ( state[i] != SAME_TRANS )
  1040.         if ( state[i] != 0 || deflink != JAMSTATE )
  1041.         {
  1042.         nxt[tblbase + i] = state[i];
  1043.         chk[tblbase + i] = statenum;
  1044.         }
  1045.  
  1046.     if ( baseaddr == firstfree )
  1047.     /* find next free slot in tables */
  1048.     for ( ++firstfree; chk[firstfree] != 0; ++firstfree )
  1049.         ;
  1050.  
  1051.     tblend = max( tblend, tbllast );
  1052.     }
  1053.  
  1054.  
  1055. /* mk1tbl - create table entries for a state (or state fragment) which
  1056.  *            has only one out-transition
  1057.  *
  1058.  * synopsis
  1059.  *   int state, sym, onenxt, onedef;
  1060.  *   mk1tbl( state, sym, onenxt, onedef );
  1061.  */
  1062.  
  1063. mk1tbl( state, sym, onenxt, onedef )
  1064. int state, sym, onenxt, onedef;
  1065.  
  1066.     {
  1067.     if ( firstfree < sym )
  1068.     firstfree = sym;
  1069.  
  1070.     while ( chk[firstfree] != 0 )
  1071.     if ( ++firstfree >= current_max_xpairs )
  1072.         expand_nxt_chk();
  1073.  
  1074.     base[state] = firstfree - sym;
  1075.     def[state] = onedef;
  1076.     chk[firstfree] = state;
  1077.     nxt[firstfree] = onenxt;
  1078.  
  1079.     if ( firstfree > tblend )
  1080.     {
  1081.     tblend = firstfree++;
  1082.  
  1083.     if ( firstfree >= current_max_xpairs )
  1084.         expand_nxt_chk();
  1085.     }
  1086.     }
  1087.  
  1088.  
  1089. /* mkprot - create new proto entry
  1090.  *
  1091.  * synopsis
  1092.  *   int state[], statenum, comstate;
  1093.  *   mkprot( state, statenum, comstate );
  1094.  */
  1095.  
  1096. mkprot( state, statenum, comstate )
  1097. int state[], statenum, comstate;
  1098.  
  1099.     {
  1100.     int i, slot, tblbase;
  1101.  
  1102.     if ( ++numprots >= MSP || numecs * numprots >= PROT_SAVE_SIZE )
  1103.     {
  1104.     /* gotta make room for the new proto by dropping last entry in
  1105.      * the queue
  1106.      */
  1107.     slot = lastprot;
  1108.     lastprot = protprev[lastprot];
  1109.     protnext[lastprot] = NIL;
  1110.     }
  1111.  
  1112.     else
  1113.     slot = numprots;
  1114.  
  1115.     protnext[slot] = firstprot;
  1116.  
  1117.     if ( firstprot != NIL )
  1118.     protprev[firstprot] = slot;
  1119.  
  1120.     firstprot = slot;
  1121.     prottbl[slot] = statenum;
  1122.     protcomst[slot] = comstate;
  1123.  
  1124.     /* copy state into save area so it can be compared with rapidly */
  1125.     tblbase = numecs * (slot - 1);
  1126.  
  1127.     for ( i = 1; i <= numecs; ++i )
  1128.     protsave[tblbase + i] = state[i];
  1129.     }
  1130.  
  1131.  
  1132. /* mktemplate - create a template entry based on a state, and connect the state
  1133.  *              to it
  1134.  *
  1135.  * synopsis
  1136.  *   int state[], statenum, comstate, totaltrans;
  1137.  *   mktemplate( state, statenum, comstate, totaltrans );
  1138.  */
  1139.  
  1140. mktemplate( state, statenum, comstate )
  1141. int state[], statenum, comstate;
  1142.  
  1143.     {
  1144.     int i, numdiff, tmpbase, tmp[CSIZE + 1];
  1145.     char transset[CSIZE + 1];
  1146.     int tsptr;
  1147.  
  1148.     ++numtemps;
  1149.  
  1150.     tsptr = 0;
  1151.  
  1152.     /* calculate where we will temporarily store the transition table
  1153.      * of the template in the tnxt[] array.  The final transition table
  1154.      * gets created by cmptmps()
  1155.      */
  1156.  
  1157.     tmpbase = numtemps * numecs;
  1158.  
  1159.     if ( tmpbase + numecs >= current_max_template_xpairs )
  1160.     {
  1161.     current_max_template_xpairs += MAX_TEMPLATE_XPAIRS_INCREMENT;
  1162.  
  1163.     ++num_reallocs;
  1164.  
  1165.     tnxt = reallocate_integer_array( tnxt, current_max_template_xpairs );
  1166.     }
  1167.  
  1168.     for ( i = 1; i <= numecs; ++i )
  1169.     if ( state[i] == 0 )
  1170.         tnxt[tmpbase + i] = 0;
  1171.     else
  1172.         {
  1173.         transset[tsptr++] = i;
  1174.         tnxt[tmpbase + i] = comstate;
  1175.         }
  1176.  
  1177.     if ( usemecs )
  1178.     mkeccl( transset, tsptr, tecfwd, tecbck, numecs );
  1179.  
  1180.     mkprot( tnxt + tmpbase, -numtemps, comstate );
  1181.  
  1182.     /* we rely on the fact that mkprot adds things to the beginning
  1183.      * of the proto queue
  1184.      */
  1185.  
  1186.     numdiff = tbldiff( state, firstprot, tmp );
  1187.     mkentry( tmp, numecs, statenum, -numtemps, numdiff );
  1188.     }
  1189.  
  1190.  
  1191. /* mv2front - move proto queue element to front of queue
  1192.  *
  1193.  * synopsis
  1194.  *   int qelm;
  1195.  *   mv2front( qelm );
  1196.  */
  1197.  
  1198. mv2front( qelm )
  1199. int qelm;
  1200.  
  1201.     {
  1202.     if ( firstprot != qelm )
  1203.     {
  1204.     if ( qelm == lastprot )
  1205.         lastprot = protprev[lastprot];
  1206.  
  1207.     protnext[protprev[qelm]] = protnext[qelm];
  1208.  
  1209.     if ( protnext[qelm] != NIL )
  1210.         protprev[protnext[qelm]] = protprev[qelm];
  1211.  
  1212.     protprev[qelm] = NIL;
  1213.     protnext[qelm] = firstprot;
  1214.     protprev[firstprot] = qelm;
  1215.     firstprot = qelm;
  1216.     }
  1217.     }
  1218.  
  1219.  
  1220. /* ntod - convert an ndfa to a dfa
  1221.  *
  1222.  * synopsis
  1223.  *    ntod();
  1224.  *
  1225.  *  creates the dfa corresponding to the ndfa we've constructed.  the
  1226.  *  dfa starts out in state #1.
  1227.  */
  1228. ntod()
  1229.  
  1230.     {
  1231.     int *accset, ds, nacc, newds;
  1232.     int duplist[CSIZE + 1], sym, hashval, numstates, dsize;
  1233.     int targfreq[CSIZE + 1], targstate[CSIZE + 1], state[CSIZE + 1];
  1234.     int *nset, *dset;
  1235.     int targptr, totaltrans, i, comstate, comfreq, targ;
  1236.     int *epsclosure(), snstods(), symlist[CSIZE + 1];
  1237.  
  1238.     /* this is so find_table_space(...) will know where to start looking in
  1239.      * chk/nxt for unused records for space to put in the state
  1240.      */
  1241.     if ( fullspd )
  1242.     firstfree = 0;
  1243.  
  1244.     accset = allocate_integer_array( accnum + 1 );
  1245.     nset = allocate_integer_array( current_max_dfa_size );
  1246.  
  1247.     todo_head = todo_next = 0;
  1248.  
  1249. #define ADD_QUEUE_ELEMENT(element) \
  1250.     if ( ++element >= current_max_dfas ) \
  1251.         { /* check for queue overflowing */ \
  1252.         if ( todo_head == 0 ) \
  1253.         increase_max_dfas(); \
  1254.         else \
  1255.         element = 0; \
  1256.         }
  1257.  
  1258. #define NEXT_QUEUE_ELEMENT(element) ((element + 1) % (current_max_dfas + 1))
  1259.  
  1260.     for ( i = 0; i <= CSIZE; ++i )
  1261.     {
  1262.     duplist[i] = NIL;
  1263.     symlist[i] = false;
  1264.     }
  1265.  
  1266.     for ( i = 0; i <= accnum; ++i )
  1267.     accset[i] = NIL;
  1268.  
  1269.     if ( trace )
  1270.     {
  1271.     dumpnfa( scset[1] );
  1272.     fputs( "\n\nDFA Dump:\n\n", stderr );
  1273.     }
  1274.  
  1275.     inittbl();
  1276.  
  1277.     if ( fullspd )
  1278.     {
  1279.     for ( i = 0; i <= numecs; ++i )
  1280.         state[i] = 0;
  1281.     place_state( state, 0, 0 );
  1282.     }
  1283.  
  1284.     if ( fulltbl )
  1285.     {
  1286.     /* declare it "short" because it's a real long-shot that that
  1287.      * won't be large enough
  1288.      */
  1289.     printf( "static short int %c[][%d] =\n    {\n", NEXTARRAY,
  1290.         numecs + 1 ); /* '}' so vi doesn't get too confused */
  1291.  
  1292.     /* generate 0 entries for state #0 */
  1293.     for ( i = 0; i <= numecs; ++i )
  1294.         mk2data( 0 );
  1295.  
  1296.     /* force ',' and dataflush() next call to mk2data */
  1297.     datapos = NUMDATAITEMS;
  1298.  
  1299.     /* force extra blank line next dataflush() */
  1300.     dataline = NUMDATALINES;
  1301.     }
  1302.  
  1303.     /* create the first states */
  1304.  
  1305.     for ( i = 1; i <= lastsc * 2; ++i )
  1306.     {
  1307.     numstates = 1;
  1308.  
  1309.     /* for each start condition, make one state for the case when
  1310.      * we're at the beginning of the line (the '%' operator) and
  1311.      * one for the case when we're not
  1312.      */
  1313.     if ( i % 2 == 1 )
  1314.         nset[numstates] = scset[(i / 2) + 1];
  1315.     else
  1316.         nset[numstates] = mkbranch( scbol[i / 2], scset[i / 2] );
  1317.  
  1318.     nset = epsclosure( nset, &numstates, accset, &nacc, &hashval );
  1319.  
  1320.     if ( snstods( nset, numstates, accset, nacc, hashval, &ds ) )
  1321.         {
  1322.         numas = numas + nacc;
  1323.         totnst = totnst + numstates;
  1324.  
  1325.         todo[todo_next] = ds;
  1326.         ADD_QUEUE_ELEMENT(todo_next);
  1327.         }
  1328.     }
  1329.  
  1330.     if ( fulltbl )
  1331.     {
  1332.     if ( ! snstods( nset, 0, accset, 0, 0, &end_of_buffer_state ) )
  1333.         flexfatal( "could not create unique end-of-buffer state" );
  1334.  
  1335.     numas += 1;
  1336.  
  1337.     todo[todo_next] = end_of_buffer_state;
  1338.     ADD_QUEUE_ELEMENT(todo_next);
  1339.     }
  1340.  
  1341.     while ( todo_head != todo_next )
  1342.     {
  1343.     targptr = 0;
  1344.     totaltrans = 0;
  1345.  
  1346.     for ( i = 1; i <= numecs; ++i )
  1347.         state[i] = 0;
  1348.  
  1349.     ds = todo[todo_head];
  1350.     todo_head = NEXT_QUEUE_ELEMENT(todo_head);
  1351.  
  1352.     dset = dss[ds];
  1353.     dsize = dfasiz[ds];
  1354.  
  1355.     if ( trace )
  1356.         fprintf( stderr, "state # %d:\n", ds );
  1357.  
  1358.     sympartition( dset, dsize, symlist, duplist );
  1359.  
  1360.     for ( sym = 1; sym <= numecs; ++sym )
  1361.         {
  1362.         if ( symlist[sym] )
  1363.         {
  1364.         symlist[sym] = 0;
  1365.  
  1366.         if ( duplist[sym] == NIL )
  1367.             { /* symbol has unique out-transitions */
  1368.             numstates = symfollowset( dset, dsize, sym, nset );
  1369.             nset = epsclosure( nset, &numstates, accset,
  1370.                        &nacc, &hashval );
  1371.  
  1372.             if ( snstods( nset, numstates, accset,
  1373.                   nacc, hashval, &newds ) )
  1374.             {
  1375.             totnst = totnst + numstates;
  1376.             todo[todo_next] = newds;
  1377.             ADD_QUEUE_ELEMENT(todo_next);
  1378.             numas = numas + nacc;
  1379.             }
  1380.  
  1381.             state[sym] = newds;
  1382.  
  1383.             if ( trace )
  1384.             fprintf( stderr, "\t%d\t%d\n", sym, newds );
  1385.  
  1386.             targfreq[++targptr] = 1;
  1387.             targstate[targptr] = newds;
  1388.             ++numuniq;
  1389.             }
  1390.  
  1391.         else
  1392.             {
  1393.             /* sym's equivalence class has the same transitions
  1394.              * as duplist(sym)'s equivalence class
  1395.              */
  1396.             targ = state[duplist[sym]];
  1397.             state[sym] = targ;
  1398.  
  1399.             if ( trace )
  1400.             fprintf( stderr, "\t%d\t%d\n", sym, targ );
  1401.  
  1402.             /* update frequency count for destination state */
  1403.  
  1404.             i = 0;
  1405.             while ( targstate[++i] != targ )
  1406.             ;
  1407.  
  1408.             ++targfreq[i];
  1409.             ++numdup;
  1410.             }
  1411.  
  1412.         ++totaltrans;
  1413.         duplist[sym] = NIL;
  1414.         }
  1415.         }
  1416.  
  1417.     numsnpairs = numsnpairs + totaltrans;
  1418.  
  1419.     if ( caseins && ! useecs )
  1420.         {
  1421.         register int j;
  1422.  
  1423.         for ( i = 'A', j = 'a'; i <= 'Z'; ++i, ++j )
  1424.         state[i] = state[j];
  1425.         }
  1426.  
  1427.     if ( fulltbl )
  1428.         {
  1429.         /* supply array's 0-element */
  1430.         if ( ds == end_of_buffer_state )
  1431.         mk2data( 0 );
  1432.         else
  1433.         mk2data( end_of_buffer_state );
  1434.  
  1435.         for ( i = 1; i <= numecs; ++i )
  1436.         mk2data( state[i] );
  1437.  
  1438.         /* force ',' and dataflush() next call to mk2data */
  1439.         datapos = NUMDATAITEMS;
  1440.  
  1441.         /* force extra blank line next dataflush() */
  1442.         dataline = NUMDATALINES;
  1443.         }
  1444.  
  1445.         else if ( fullspd )
  1446.         place_state( state, ds, totaltrans );
  1447.  
  1448.     else
  1449.         {
  1450.         /* determine which destination state is the most common, and
  1451.          * how many transitions to it there are
  1452.          */
  1453.  
  1454.         comfreq = 0;
  1455.         comstate = 0;
  1456.  
  1457.         for ( i = 1; i <= targptr; ++i )
  1458.         if ( targfreq[i] > comfreq )
  1459.             {
  1460.             comfreq = targfreq[i];
  1461.             comstate = targstate[i];
  1462.             }
  1463.  
  1464.         bldtbl( state, ds, totaltrans, comstate, comfreq );
  1465.         }
  1466.     }
  1467.  
  1468.     if ( fulltbl )
  1469.     dataend();
  1470.  
  1471.     else
  1472.     {
  1473.     cmptmps();  /* create compressed template entries */
  1474.  
  1475.     /* create tables for all the states with only one out-transition */
  1476.     while ( onesp > 0 )
  1477.         {
  1478.         mk1tbl( onestate[onesp], onesym[onesp], onenext[onesp],
  1479.             onedef[onesp] );
  1480.         --onesp;
  1481.         }
  1482.  
  1483.     mkdeftbl();
  1484.     }
  1485.     
  1486.     }
  1487.  
  1488.  
  1489. /* place_state - place a state into full speed transition table
  1490.  *
  1491.  * synopsis
  1492.  *     int *state, statenum, transnum;
  1493.  *     place_state( state, statenum, transnum );
  1494.  *
  1495.  * State is the statenum'th state.  It is indexed by equivalence class and
  1496.  * gives the number of the state to enter for a given equivalence class.
  1497.  * Transnum is the number of out-transitions for the state.
  1498.  */
  1499.  
  1500. place_state( state, statenum, transnum )
  1501. int *state, statenum, transnum;
  1502.  
  1503.     {
  1504.     register int i;
  1505.     register int *state_ptr;
  1506.     int position = find_table_space( state, transnum );
  1507.  
  1508.     /* base is the table of start positions */
  1509.     base[statenum] = position;
  1510.  
  1511.     /* put in action number marker; this non-zero number makes sure that
  1512.      * find_table_space() knows that this position in chk/nxt is taken
  1513.      * and should not be used for another accepting number in another state
  1514.      */
  1515.     chk[position - 1] = 1;
  1516.  
  1517.     /* put in end-of-buffer marker; this is for the same purposes as above */
  1518.     chk[position] = 1;
  1519.  
  1520.     /* place the state into chk and nxt */
  1521.     state_ptr = &state[1];
  1522.  
  1523.     for ( i = 1; i <= numecs; ++i, ++state_ptr )
  1524.     if ( *state_ptr != 0 )
  1525.         {
  1526.         chk[position + i] = i;
  1527.         nxt[position + i] = *state_ptr;
  1528.         }
  1529.  
  1530.     if ( position + numecs > tblend )
  1531.     tblend = position + numecs;
  1532.     }
  1533.  
  1534.  
  1535. /* stack1 - save states with only one out-transition to be processed later
  1536.  *
  1537.  * synopsis
  1538.  *   int statenum, sym, nextstate, deflink;
  1539.  *   stack1( statenum, sym, nextstate, deflink );
  1540.  *
  1541.  * if there's room for another state one the "one-transition" stack, the
  1542.  * state is pushed onto it, to be processed later by mk1tbl.  If there's
  1543.  * no room, we process the sucker right now.
  1544.  */
  1545.  
  1546. stack1( statenum, sym, nextstate, deflink )
  1547. int statenum, sym, nextstate, deflink;
  1548.  
  1549.     {
  1550.     if ( onesp >= ONE_STACK_SIZE )
  1551.     mk1tbl( statenum, sym, nextstate, deflink );
  1552.  
  1553.     else
  1554.     {
  1555.     ++onesp;
  1556.     onestate[onesp] = statenum;
  1557.     onesym[onesp] = sym;
  1558.     onenext[onesp] = nextstate;
  1559.     onedef[onesp] = deflink;
  1560.     }
  1561.     }
  1562.  
  1563.  
  1564. /* tbldiff - compute differences between two state tables
  1565.  *
  1566.  * synopsis
  1567.  *   int state[], pr, ext[];
  1568.  *   int tbldiff, numdifferences;
  1569.  *   numdifferences = tbldiff( state, pr, ext )
  1570.  *
  1571.  * "state" is the state array which is to be extracted from the pr'th
  1572.  * proto.  "pr" is both the number of the proto we are extracting from
  1573.  * and an index into the save area where we can find the proto's complete
  1574.  * state table.  Each entry in "state" which differs from the corresponding
  1575.  * entry of "pr" will appear in "ext".
  1576.  * Entries which are the same in both "state" and "pr" will be marked
  1577.  * as transitions to "SAME_TRANS" in "ext".  The total number of differences
  1578.  * between "state" and "pr" is returned as function value.  Note that this
  1579.  * number is "numecs" minus the number of "SAME_TRANS" entries in "ext".
  1580.  */
  1581.  
  1582. int tbldiff( state, pr, ext )
  1583. int state[], pr, ext[];
  1584.  
  1585.     {
  1586.     register int i, *sp = state, *ep = ext, *protp;
  1587.     register int numdiff = 0;
  1588.  
  1589.     protp = &protsave[numecs * (pr - 1)];
  1590.  
  1591.     for ( i = numecs; i > 0; --i )
  1592.     {
  1593.     if ( *++protp == *++sp )
  1594.         *++ep = SAME_TRANS;
  1595.     else
  1596.         {
  1597.         *++ep = *sp;
  1598.         ++numdiff;
  1599.         }
  1600.     }
  1601.  
  1602.     return ( numdiff );
  1603.     }
  1604.